package junior.图;

import java.util.Scanner;

public class queen8_01 {
    static int[] queen_position = new int[13];
    static int[][] c= new int[3][26];//k控制行，c[0][i]标记列，c[1][k+i]标记45度斜线，c[2][k+i-n]标记135度斜线(0:未标记，1：标记)
    static int count=0,n;   //存储每种可行的结果  n：棋盘大小
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (1 == 1){
            n = input.nextInt();
            long startTime = System.currentTimeMillis();
            queen(0);
            long endTime = System.currentTimeMillis();
            System.out.println("总方案数："+count);
            System.out.println(endTime -startTime);
            count = 0;
        }
    }
    static void queen(int k) {
        int i;
        if (k == n) {
            // for (i = 0; i < n; i++)
            //     System.out.print(queen_position[i] + 1 +" ");
            // System.out.println();
            count++;
            return;
        }
        for (i = 0; i < n; i++) {  //queen_position[k] 找到一组解后，数据被覆盖
            if ((0 == c[0][i]) && (0 == c[1][k + i]) && (0 == c[2][k - i + n])) {
                queen_position[k] = i;
                c[0][i] = 1;
                c[1][k + i] = 1;
                c[2][k - i + n] = 1;
                queen(k + 1);
                c[0][i] = 0;
                c[1][k + i] = 0;
                c[2][k - i + n] = 0;
            }
        }
    }
}
